⟸ pàgina anterior ⟸
Exercici 7 (Tasca 2).
(regular languages, homomorphism, minimization of DFAs)

L’homomorfisme invers d’un llenguatge regular és regular

  1. Demostreu que L=\{w \in \{0,1\}^* \mid \mathtt{value}_2(w)\in 3 \mathbb N\} és un llenguatge regular. Calculeu de forma explícita el DFA mínim per al llenguatge \sigma^{-1}(L), on \sigma: \{a,b,c\}\to \{0,1\} és l’homomorfirme definit per

    1. \sigma(a)=01,
      \sigma(b)=0 i
      \sigma(c)=\lambda.
    2. \sigma(a)=10,
      \sigma(b)=0 i
      \sigma(c)=\lambda.
    3. \sigma(a)=00,
      \sigma(b)=11 i
      \sigma(c)=\lambda.
    4. \sigma(a)=001,
      \sigma(b)=101 i
      \sigma(c)=0.

    Recordeu que, donat un DFA A i un morfisme \sigma, és possible construir un DFA A' que reconegui el llenguatge \sigma^{-1}(L(A)) de la manera següent: amb entrada w, A' executa A sobre entrada \sigma(w) i accepta si ho fa A.

  2. Donat un DFA A i un homomorfisme \sigma, quin és el cost de construir un DFA per al llenguatge \sigma^{-1}(L(A))?

  3. Suposeu que es construeix un DFA per a \sigma^{-1}(L(A)) partint d’un DFA A mínim. És també mínim el DFA resultant?

  4. Funciona també la construcció usada per obtenir el DFA per a \sigma^{-1}(L(A)) en cas que A sigui un NFA?